翻訳と辞書
Words near each other
・ Random-access stored-program machine
・ Random-access Turing machine
・ Random.org
・ Randomajestiq
・ Randominta
・ Randomization
・ Randomization function
・ Randomized algorithm
・ Randomized algorithms as zero-sum games
・ Randomized block design
・ Randomized controlled trial
・ Randomized experiment
・ Randomized Hough transform
・ Randomized meldable heap
・ Randomized response
Randomized rounding
・ Randomized weighted majority algorithm
・ Randomness
・ Randomness extractor
・ Randomness merger
・ Randomness tests
・ Random—Burin—St. George's
・ Randon
・ Randonnai
・ Randonneuring
・ Randonneurs USA
・ Randonnée
・ Randoon
・ Randor
・ Randor Bierd


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Randomized rounding : ウィキペディア英語版
Randomized rounding

Within computer science and operations research,
many combinatorial optimization problems are computationally intractable to solve exactly (to optimality).
Many such problems do admit fast (polynomial time) approximation algorithms—that is, algorithms that are guaranteed to return an approximately optimal solution given any input.
Randomized rounding
is a widely used approach for designing and analyzing such approximation algorithms.〔
〕〔

The basic idea is to use the probabilistic method
to convert an optimal solution of a relaxation
of the problem into an approximately optimal solution to the original problem.
== Overview ==
The basic approach has three steps:
# Formulate the problem to be solved as an integer linear program (ILP).
# Compute an optimal fractional solution x to the linear programming relaxation (LP) of the ILP.
# Round the fractional solution x of the LP to an integer solution x' of the ILP.
(Although the approach is most commonly applied with linear programs,
other kinds of relaxations are sometimes used.
For example, see Goeman's and Williamson's semi-definite programming-based
Max-Cut approximation algorithm.)
The challenge in the first step is to choose a suitable integer linear program.
Familiarity with linear programming is required, in particular, familiarity with
how to model problems using linear programs and integer linear programs.
But, for many problems, there is a natural integer linear program that works well,
such as in the Set Cover example below. (The integer linear program should have a small
integrality gap;
indeed randomized rounding is often used to prove bounds on integrality gaps.)
In the second step, the optimal fractional solution can typically be computed
in polynomial time
using any standard linear programming algorithm.
In the third step, the fractional solution must be converted into an integer solution
(and thus a solution to the original problem).
This is called ''rounding'' the fractional solution.
The resulting integer solution should (provably) have cost
not much larger than the cost of the fractional solution.
This will ensure that the cost of the integer solution
is not much larger than the cost of the optimal integer solution.
The main technique used to do the third step (rounding) is to use randomization,
and then to use probabilistic arguments to bound the increase in cost due to the rounding
(following the probabilistic method from combinatorics).
There, probabilistic arguments are used to show the existence of discrete structures with
desired properties. In this context, one uses such arguments to show the following:
: ''Given any fractional solution x of the LP, with positive probability the randomized rounding process produces an integer solution x' that approximates x'' according to some desired criterion.
Finally, to make the third step computationally efficient,
one either shows that x' approximates x
with high probability (so that the step can remain randomized)
or one derandomizes the rounding step,
typically using the method of conditional probabilities.
The latter method converts the randomized rounding process
into an efficient deterministic process that is guaranteed
to reach a good outcome.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Randomized rounding」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.